package com.czk.tree.binarysorttree;

import lombok.Data;

/**
 * 二叉排序树
 *
 * @Author:ChenZhangKun
 * @Date: 2020/7/12 19:21
 */
public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9};
        BinarySortTree binarySortTree = new BinarySortTree();
        // 加入节点
        for (int i : arr) {
            binarySortTree.add(new Node(i));
        }
        binarySortTree.add(new Node(0));
        // 遍历二叉排序树
        binarySortTree.inOrderTraverse();
        binarySortTree.add(new Node(8));
        System.out.println("============");
        binarySortTree.inOrderTraverse();
        binarySortTree.deleteNode(9);
        System.out.println("============");
        binarySortTree.inOrderTraverse();
    }
}

class BinarySortTree {
    private Node root;

    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    // 中序遍历
    public void inOrderTraverse() {
        if (root != null) {
            root.inOrderTraverse();
        }
    }

    // 查找要删除的父节点
    public Node searchParent(int value) {
        if (root != null) {
            return root.searchParent(value);
        } else {
            return null;
        }
    }

    // 查找要删除的节点
    public Node search(int value) {
        if (root != null) {
            return root.search(value);
        } else {
            return null;
        }
    }

    // 删除节点
    public void deleteNode(int value) {
        // targetNode没有父节点的情况
        if (root == null) {
            return;
        }
        if (root.value == value && root.left == null && root.right == null) {
            root = null;
        } else {
            // 找到targetNode
            Node targetNode = root.search(value);
            if (targetNode == null) return;
            // 找到父节点
            Node nodeParent = this.searchParent(value);
            System.out.println("找到父节点" + nodeParent);
            // 1 第一种情况，目标节点是叶子节点的情况
            // 判断targetNode是左子节点还是右子节点
            if (targetNode.left == null && targetNode.right == null) {
                // 叶子节点
                if (nodeParent.left != null && nodeParent.left.value == value) {
                    // 左子节点
                    nodeParent.left = null;
                } else if (nodeParent.right != null && nodeParent.right.value == value) {
                    nodeParent.right = null;
                }
                // 2 第二种情况，目标节点有两个子节点的情况
            } else if (targetNode.left != null && targetNode.right != null) {
                // 拥有两个子树
                // 使用目标节点的右子树的最小值覆盖目标值，并将该值赋值为null
                int i = this.deleteRightTreeMin(targetNode.right);
                // 右边最小的值覆盖需要删除的值
                targetNode.value = i;
            } else {
                // 3 第三个情况，只拥有一个子树
                // 只有左子节点
                if (targetNode.left != null) {
                    // 如果targetNode是parent的左子节点
                    if (nodeParent != null && nodeParent.left.value == value) {
                        // 挂载左节点
                        nodeParent.left = targetNode.left;
                    } else if (nodeParent != null && nodeParent.right.value == value) {
                        // 挂载到右节点
                        nodeParent.right = targetNode.left;
                    } else {
                        // 根节点为空的情况
                        root = targetNode.left;
                    }
                } else {
                    // 如果targetNode是parent的右子节点
                    if (nodeParent != null && nodeParent.left.value == value) {
                        nodeParent.left = targetNode.right;
                    } else if (nodeParent != null) {
                        nodeParent.right = targetNode.right;
                    } else {
                        // 根节点为空的情况
                        root = targetNode.right;
                    }
                }
            }

        }
    }

    /**
     * @param node 查找的节点
     * @return 该树的最小值
     */
    public int deleteRightTreeMin(Node node) {
        Node target = node;
        while (target.left != null) {
            target = target.left;
        }
        // 删除最小节点
        this.deleteNode(target.value);
        return target.value;
    }
}

@Data
class Node {
    // 值
    int value;
    // 左节点
    Node left;
    // 右节点
    Node right;

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    // 查找节点
    public Node search(int value) {
        if (value == this.value) {
            // 找到该节点
            return this;
        } else if (value < this.value) {
            // 不是当前节点,向左子树递归查找
            if (this.left != null) {
                return this.left.search(value);
            }
        } else {
            // 向右递归查找
            if (this.right != null) {
                return this.right.search(value);
            }
        }
        return null;
    }

    // 查找要删除节点的父节点
    public Node searchParent(int value) {
        // 左节点不为空或者右节点不为空
        if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
            return this;
        } else {
            // 返回值
            if (value < this.value && this.left != null) {
                return this.left.searchParent(value);
            } else if (value >= this.value && this.right != null) {
                // 返回值
                return this.right.searchParent(value);
            }
        }
        return null;
    }

    public Node(int value) {
        this.value = value;
    }

    // 添加节点
    // 递归的形式添加节点，需要满足二叉排序树的特点
    public void add(Node node) {
        // 节点是否为空
        if (node == null) {
            return;
        }
        // 判断传入的值和当前节点的值关系
        if (node.value < this.value) {
            // 左节点为空，挂载在左节点
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else if (this.value < node.value) {
            // 添加到右节点
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
    }

    // 中序遍历
    public void inOrderTraverse() {
        if (this.left != null) {
            this.left.inOrderTraverse();
        }
        System.out.println(this);
        if (this.right != null)
            this.right.inOrderTraverse();
    }
}
